package xyz.naokeziteng.data_structure.graph_theory;

import java.util.Arrays;

/**
 * @author hawk
 * @date 2022/10/12
 * @desc
 **/
public class BipartiteGraph {
    //蓝色
    private static final int BLUE = 0;
    //绿色
    private static final int GREEN = 1;

    private Graph G;
    private boolean[] visited;

    //颜色
    private int[] colors;
    //是否二分
    private boolean isBipartite;

    /**
     * @param G 图
     */
    public BipartiteGraph(Graph G) {
        this.G = G;
        this.isBipartite = true;
        this.visited = new boolean[G.V()];
        this.colors = new int[G.V()];
        Arrays.fill(this.colors, -1);
        for (int v = 0; v < G.V(); v++) {
            if (!visited[v]) {
                dfs(v, v);
                if (!isBipartite) {
                    break;
                }
            }
        }
    }

    //二分图检测
    private void dfs(int v, int parent) {
        visited[v] = true;
        if (v == parent) {
            colors[v] = BLUE;
        } else {
            colors[v] = childColor(parent);
        }
        for (int w : G.adj(v)) {
            if (!visited[w]) {
                dfs(w, v);
            } else if (colors[w] != childColor(v)) {
                this.isBipartite = false;
            }
        }
    }

    //返回邻接节点的颜色
    private int childColor(int v) {
        G.validateVertex(v);
        if (colors[v] == -1) {
            throw new IllegalArgumentException("节点未染色...");
        }
        return colors[v] == GREEN ? BLUE : GREEN;
    }

    public static void main(String[] args) {
        BipartiteGraph bg = new BipartiteGraph(new Graph("src/main/resources/g.txt"));
        System.out.println(bg.isBipartite);
        BipartiteGraph bg3 = new BipartiteGraph(new Graph("src/main/resources/g3.txt"));
        System.out.println(bg3.isBipartite);
    }
}
